package com.lwx.sort;

public class BubboSort<E extends Comparable<E>>{
    private E[] data;
    private int length;
    public BubboSort(){
        data = (E[])new Object[10];
        length = 0;
    }
    private void swap(int i, int j){
        E tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    //冒泡排序
    public void sort(E[] data){
        boolean flag = true;
        for (int i = 0; i < data.length-1 && flag; i++) {
            flag = false;
            for (int j = data.length -1; j > i; j--) {
                if(data[j].compareTo(data[j-1]) < 0){
                    swap(j,j-1);
                    flag = true;
                }
            }
        }
    }

    //简单选择排序
    public void SelectSort(E[] data){
        for (int i = 0; i < data.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < data.length; j++) {
                if(data[j].compareTo(data[minIndex]) < 0){
                    minIndex = j;
                }
                if(minIndex != i){
                    swap(minIndex,i);
                }
            }

        }
    }

    /**
     * 插入排序，元素分为有序区和无序区，从无序区中找出元素，挨个与有序区的元素进行比较，
     * 如果是从小到大排序，找到第一个比无序区小的元素，无序区的元素插在他后面
     * @param data
     */
    public void InsertSort(E[] data){
        //第0个位置存放的是哨兵，存放无序区的第一个元素
        E[] tmp = (E[])new Object[data.length + 1];
        for (int i = 0; i < data.length; i++) {
            tmp[i+1] = data[i];
        }
        //i代表无序区第一个元素的下标
        for (int i = 2; i < tmp.length; i++) {
            //只有当无序的第一个元素小于有序区的最后一个元素时，才进行交换
            //否则，无序区的第一个元素划入有序区，进行下一轮循环
            if(tmp[i].compareTo(tmp[i-1]) < 0){
                //0位置放无序区第一个元素
                tmp[0] = tmp[i];
                //j代表有序区最后一个元素
                int j;
                for (j = i-1; j >0 ; j--) {
                    //无序区元素比有序区最后一个小，进行后移
                    if(tmp[j].compareTo(tmp[0])>0){
                        tmp[j+1] = tmp[j];
                    }else {
                        break;
                    }
                }
                tmp[j+1] = tmp[0];
            }
        }
    }
}
